BOTER

BOTER-KAAS-EIEREN
- en meer-op-een-rij -

(Tic-Tac-Toe in Amerika, Noughts and Crosses in Engeland, Eck-Meck-Steck in Duitsland)

HIER kun je het spel zelf eerst spelen

Een betere naam zou natuurlijk zijn 3-op-een -rij. Het spel is nogal flauw, want het wordt altijd gelijkspel.
Voor de beginspeler zijn er (vanwege de symmetrie) maar drie mogelijke posities, namelijk:

SITUATIE 1
Twee mogelijkheden:

SITUATIE 2
Vijf mogelijkheden:

SITUATIE 3
Vijf mogelijkheden:

Ofwel: Met twee goede spelers wordt het altijd gelijk spel!
Een nogal saai spel dus. Tijd voor een variant....

Als elke speler zélf mag weten of hij een kruisje of een nulletje zet!

Dan kan de eerste speler altijd winnen door het centrale veld te bezetten.
Dan zijn er eigenlijk maar twee varianten, al naar gelang speler 2 een middenveld of een hoekveld kiest:

In deze beide optimale speelwijzen wint speler 1.
Dat roept wel meteen om de volgende variant natuurlijk:

Omgekeerd spelen!

Degene die nu het eerst 3 op een rij heeft verliest!

Speler 1 kan nu gelijk spel forceren. Vreemd genoeg is dat door wéér te beginnen in het midden.
Daar zet hij een willekeurig symbool neer.
Als hij daarna symmetrisch ten opzichte van het centrum speelt en steeds een ander symbool neerzet dan zijn tegenstander wordt het gelijkspel.

Alweer nogal saai dus.
Daarom gauw over naar het logische vervolg: Hoe is het met "4-op-een-rij" of "5-op-een-rij" , of .......?

VIER-OP-EEN-RIJ

Bij vier op een rij geldt hetzelfde: ook daar kan speler twee altijd gelijk spel maken. Het bewijs daarvan is te zien door negen velden van het 4x4 bord te markeren:

Wil je op dit veld een rij van vier maken dan zijn er drie mogelijkheden:

1.	De rij heeft drie velden in het gemarkeerde gedeelte. Dat kan speler 2 tegenhouden, dat hebben we al bij drie-op-een-rij gezien.

2.	De rij minder dan drie velden in het gemarkeerde gedeelte. Er zijn twee mogelijkheden: a. De rij loopt helemaal in de rand b. De rij loopt van rechtsboven naar linksonder. Beide varianten zijn door speler 2 makkelijk te pareren: Als speler 1 het veld rechtsboven of linksonder markeert, ga je uit van variant 2b en markeer je direct het andere veld rechtsboven of linksonder. Mocht speler 1 daarna nog een veld buiten het gemarkeerde deel kiezen, dan kun je variant 2a alsnog blokkeren door een ander veld uit dezelfde rij/kolom te kiezen. (neemt hij linksboven dan kies je één van beiden en hebt daarna nog steeds kans om te blokkeren mocht het de andere worden).

3.	Het wordt de diagonaal van rechtsboven naar linksonder.

Omdat beide varianten door speler 2 zijn tegen te houden kan speler 1 niet 4-op-een-rij krijgen

Leuker is om vier-op-een-rij driedimensionaal zelf te spelen.

VIJF - OP - EEN - RIJ

Op dezelfde manier als bij 4-op-een-rij kun je met inductie eenvoudig bewijzen dat k-op een rij ook door speler 2 altijd gelijk spel te maken is.
Het kan ook op een leuke andere manier bewezen worden. Neem 5-op-een rij en nummer de velden als hieronder.

Er zijn twaalf rijen van vijf te maken op dit bord, en ze hebben de nummers hieronder

1 - 2 - 3 - 4 - 5
6 - 7 - 8 - 9 -10
11-12-13-14-15
16-17-18-19-20
21-22-23-24-25
1 - 6 -11-16-21
2 - 7 -12-17-22
3 - 8 -13-18-23
4 - 9 -14-19-24
5-10 -15-20-25
1 - 7 -13-19-25
5 - 9 -13-17-21

Nu gaan we uit elke rij twee getallen aanwijzen en dat proberen we zo te doen dat in totaal elk getal maar één keer wordt aangewezen. Dat kan door de rode getallen in de tabel hierboven te nemen. Dat geeft dus 12 paren getallen. Zodra speler 1 één getal markeert neemt speler 2 gewoon het bijbehorende getal!
Deze tactiek zorgt er zeker voor dat geen één van de twaalf rijen compleet kan worden voor speler 1.

Bij meer-op-een-rij rijst er echter de vraag: is er altijd een serie verschillende rode getallen te vinden?

Het antwoord daarop is duidelijk: JA!
Het bewijs daarvan maakt gebruik van de stelling van Hall:

Stel je hebt een collectie A_n van n verzamelingen: A_n = {V₁,V₂,V₃,...,V_n}
Is het dan mogelijk om uit elke verzameling een verschillend element te kiezen (een vertegenwoordiger)?
Zo'n verzameling van vertegenwoordigers heet een SDR = System of Distinct Representatives

De stelling van Hall luidt:

Er is een SDR te maken van A_n

Elke collectie van k deelverzamelingen uit A_n bevat minstens k elementen

Deze stelling heet ook wel de "huwelijksstelling". Waarom dat zo is en een bewijs ervan staat hier.

Bij n - op - een - rij hebben we te maken met verzamelingen van n elementen. Verder weten we zeker dat een element in hoogstens 3 verzamelingen voorkomt, immers door elk hokje lopen hoogstens 3 rijen (horizontaal, verticaal en eventueel diagonaal).
Beschouw nu k verzamelingen uit deze collectie. Dan staan er n•k elementen achter elkaar, maar er zitten eventueel nog dubbelen tussen. Laten we het ongunstigste geval bekijken: met zoveel mogelijk dubbelen.
Als elk element er drie keer in zou staan, zijn er nog n•^k/₃ verschillenden over, en omdat n > 5 is ⁿ/₃ > ⁵/₃ > 1 dus is n•^k/₃ > k
Daarmee is bewezen dat er in het ongunstigste geval nog steeds meer dan k verschillende elementen in de collectie zijn, dus dat de huwelijksvoorwaarde geldt, dus dat er een SDR bestaat.

Maak zo'n SDR en haal vervolgens al deze elementen uit de verzamelingen V. Dan houden we verzamelingen van elk n -1 elementen over (immers uit elke oorspronkelijke is er precies 1 weggehaald).
Volgens eenzelfde redenering staan er dan in een collectie van k verzamelingen daaruit in totaal (n-1)•k elementen waar nog dubbelen bij kunnen staan. Elk element staat in hoogstens 3 verzamelingen, dus er zijn in het ongunstigste geval (n - 1)•^k/₃ verschillende elementen over. Weer geldt dat, omdat n > 5, ^(n-1)/₃ > ⁴/₃ > 1 dus weer is aan de huwelijksvoorwaarde voldaan, dus weer is een SDR te vinden.

De twee te vinden SDR's vormen samen de gevraagde serie tweetallen waarmee n-op-een-rij nooit door speler 1 gewonnen kan worden. Speler 2 kan altijd gelijk spel forceren.

Boter Kaas en Eieren verdekt opgesteld.

Haal uit een kaartspel de kaarten A,2,3,4,5,6,7,8,9.
De Aas telt voor 1.
Leg deze kaarten open op tafel en speel het volgende spel:
Om de beurt gaan wij een kaart pakken en wie na drie kaarten precies 15 punten heeft verzameld heeft gewonnen.
Heb je het door???
Zie jij intussen als echte expert dat we gewoon boter kaas en eieren zitten te spelen?
NEE????

Misschien helpt het dan als we de kaarten zó neerleggen:

JAWEL!
Hier ligt een tovervierkant! De som van alle rijen en alle kolommen en beide diagonalen is 15.
Dus wie het eerst 3-op-een-rij heeft, heeft samen 15 punten verzameld. Gewoon Boter-Kaas en Eieren dus!

Toch nog een raadsel!

Oké, ik geef het toe; ik kan het niet laten, het is een verslaving.
Hier toch nog maar een raadseltje over boter-kaas-eieren.
Twee goede spelers hebben op een gegeven moment de volgende stand bereikt:

De simpele vraag is: Wie gaat er winnen?

Oplossing

Het lijkt erop alsof deze vraagt niet te beantwoorden is, omdat je niet weet wie er aan de beurt is.
Maar dat is niet zo. Stel dat "Kruisje" aan de beurt is. Dan heeft dus "Nulletje" het laatste teken gezet.
Laten we terugreizen in de tijd.
Hoe zag de stand er vóór dat laatste kruisje uit?
Er zijn drie mogelijkheden:

De eerste en tweede zijn onmogelijk, want als "Nulletje" een goede speler was, dan had hij in figuur 1 wel direct gewonnen en in figuur 2 wel rechtsonder geblokkeerd.
De vorige stand moet dus zeker de derde van de drie zijn geweest.
Laten we weer een stapje terugnemen in de tijd.....
Vanaf de eerste stand hierboven zijn er weer drie mogelijke vorige standen (met "kruisje" aan de beurt):

In alle gevallen had "Kruisje" iets anders gedaan (namelijk gewonnen).
Kortom: kruisje is niet aan de beurt (ha; een bewijs uit het ongerijmde).
Dus nulletje is nu aan de beurt (ga op de zelfde manier maar na dat er nu wél een mogelijk spelverloop is).
Dus Nulletje gaat ook winnen door nu rechtsboven een rij te maken.